package oj;

import java.util.Deque;
import java.util.LinkedList;

//有效的括号：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
//有效字符串需满足：
//左括号必须用相同类型的右括号闭合。
//左括号必须以正确的顺序闭合。
//每个右括号都有一个对应的相同类型的左括号。
public class Solution_20 {
    private static boolean isMatch(char left,char right){
        if(left == '(' && right == ')'){
            return true;
        }
        if(left == '[' && right == ']'){
            return true;
        }
        if(left == '{' && right == '}'){
            return true;
        }
        return false;
    }
    //进行每一个字符的遍历
    //遇到左括号就入栈，遇到右括号就将栈顶元素拿出来对比，是否匹配
    //将所有字符都遍历结束后，如果栈中还有元素，则说明左括号多出来了，返回false
    public static boolean isValid(String s) {
        Deque<Character> stack = new LinkedList<>();

        //遍历字符串方法有两种：
        //方法一：toCharArray():将字符串对象中的字符转换为一个字符数组
//        char[] array = s.toCharArray();
//        for(char c:array){}

        //方法二：charAt():指定位置的字符输出
//        int len = s.length();
//        for (int i = 0; i < len; i++) {
//            char c = s.charAt(i);
//        }

        char[] array = s.toCharArray();
        for(char c : array){
            //判断 c 是左括号还是右括号
            if(c == '(' || c == '[' || c == '{'){
                stack.push(c);
            }else{
                //判断栈是否为空
                if(stack.isEmpty()){
                    return false;
                }
                //取出栈顶元素，进行判断是否匹配
                char left = stack.pop();
                if(!isMatch(left,c)){
                    //不匹配返回false
                    return false;
                }
                //匹配则进行下一个字符的判断
            }
        }
        if(stack.isEmpty()){
            return true;
        }else{
            return false;
        }
    }

    public static void main(String[] args) {
        String s = "{[{[(())]}]}";
        String e = "([{[]}])";
        String a = "{[[]])()";
        System.out.println(isValid(a));
        System.out.println(isValid(e));
        System.out.println(isValid(s));
    }
}
